package heap;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description: 堆的习题
 * User: 王圆豪
 * Date: 2024-09-21
 * Time: 16:35
 */

//最小k个数
public class Solution {
    static class siftB implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2){
            return o2 - o1;
        }
    }

    public int[] smallestK(int[] arr, int k) {
        int[] a = new int[k];
        if(k == 0){
            return a;
        }
        siftB s = new siftB();
        Queue<Integer> p = new PriorityQueue<>(k, s);
        for (int i = 0; i < k; i++) {
            p.add(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if (p.peek() > arr[i]){
                p.poll();
                p.add(arr[i]);
            }
        }
        for (int i = k - 1; i >= 0; i--) {
            a[i] = p.poll();
        }
        return a;
    }
}
